github.com/captn3m0/codechef.git

---
category_name: challenge
problem_code: FAULT
problem_name: 'Fault Tolerance'
languages_supported:
    - C
    - CPP14
    - JAVA
    - PYTH
    - 'PYTH 3.5'
    - CS2
    - 'PAS fpc'
    - 'PAS gpc'
    - RUBY
    - PHP
    - GO
    - NODEJS
    - HASK
    - SCALA
    - D
    - PERL
    - FORT
    - WSPC
    - ADA
    - CAML
    - ICK
    - BF
    - ASM
    - CLPS
    - PRLG
    - ICON
    - 'SCM qobi'
    - PIKE
    - ST
    - NICE
    - LUA
    - BASH
    - NEM
    - 'LISP sbcl'
    - 'LISP clisp'
    - 'SCM guile'
    - JS
    - ERL
    - TCL
    - PERL6
    - TEXT
    - CLOJ
    - FS
max_timelimit: '1'
source_sizelimit: '50000'
problem_author: pieguy
problem_tester: laycurse
date_added: 7-02-2013
tags:
    - april13
    - bitwise
    - challenge
    - gauss
    - pieguy
editorial_url: 'http://discuss.codechef.com/problems/FAULT'
time:
    view_start_date: 1366018200
    submit_start_date: 1366018200
    visible_start_date: 1366018200
    end_date: 1735669800
    current: 1525199663
is_direct_submittable: false
layout: problem
---
All submissions for this problem are available.Chef has a set of very large set of very important data he doesn't want to lose. Chef has a number of servers on which he stores the data. To store the data, Chef begins by splitting his data into chunks. Then he assigns a set of chunks to each server. For the sake of redundancy, the same chunk may be assigned to multiple servers. If multiple chunks are assigned to the same server, there will not be enough space to store all of the chunks individually, so instead the chunks are combined together. When multiple chunks are combined together it is no longer possible to retrieve the data from the original chunks. However, by combining data from multiple servers it may be possible to retrieve the original data.

Denote **A ⊕ B** as the result of combining chunks **A** and **B**. The following properties hold:

- **A ⊕ B = B ⊕ A**
- **(A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)**
- **(A ⊕ A) ⊕ B = B**

Note that the first two properties imply that when combining more than two chunks, the order in which they are combined does not matter.

Let's consider an example (this example will coincide with the sample input below). There are **4** chunks of data, and **6** servers. Denote **Ci (0 ≤ i < 4)** as the original chunks of data, and **Sj (0 ≤ j < 6)** as the data stored on the servers. Chef combines chunks as follows:

- **S0 = C2**
- **S1 = C0 ⊕ C3**
- **S2 = C0 ⊕ C2**
- **S3 = C1 ⊕ C3**
- **S4 = C0 ⊕ C1 ⊕ C2**
- **S5 = C0 ⊕ C1**

One way Chef may recover the original data is as follows:

- **C0 = S0 ⊕ S2**
- **C1 = S2 ⊕ S4**
- **C2 = S0**
- **C3 = S2 ⊕ S3 ⊕ S4**

Chef is now interested in how safe his data is. If the data from some servers is lost it may be impossible to recover the original data. Chef would like you to find a set of servers such that simultaneous failure would make some part of his data irrecoverable. Chef prefers that you find a small set of servers, but does not require minimality. Smaller sets will score more points.

### Input

Each test file contains only one test case.

The first line of input contains **2** space-separated integers **N** and **S**, denoting the number of chunks and number of servers, respectively. Then **S** lines follow, each with a description of the chunks stored on one server. A server description consists of an integer **C** denoting the number of chunks assigned to this server, followed by **C** integers denoting the ids of the chunks assigned to this server. Chunks are numbered from 0 to **N−1** and servers numbered 0 to **S−1**.

### Output

First output an integer **K**, the number of failing servers in your solution. Then output the distinct ids of the failing servers.

### Constraints

- **50 ≤ N ≤ 200**
- **2\*N ≤ S ≤ 1000**
- **1 ≤ C ≤ N**
- Each server stores distinct chunks.
- Chef can recover the original data if no servers are lost.
- All official test files are generated by the method written in Test Case Generation.

Note that the following Sample Input does not satisfy the constraints.

### Scoring

Your score for each test file is **10\*K/(S−N+1)**. The total score is the average of scores over all test files. The goal is to minimize your score.

### Example

<pre>
<b>Input:</b>
4 6
1 2
2 0 3
2 0 2
2 1 3
3 0 1 2
2 0 1

<b>Output:</b>
1
2
</pre>### Explanation

This sample output would score **10\*1/(6−4+1) = 3.333...**. If server **2** is lost, there is no way to recover data chunks 0, **1**, or **3**.

### Test Case Generation

The judge has **40** official test files.

An integer **N** is chosen randomly and uniformly between **50** and **200**, inclusive. Then an integer **S** is chosen randomly and uniformly between **2\*N** and **1000**, inclusive. A real number **P** is chosen randomly and uniformly between **0.3** and **0.8**, inclusive, and each chunk is assigned to each server with probability **P**. The order of the chunks assigned to each server is shuffled.

If a generated test does not satisfy the constraints, then the test is discarded.