B - Everyone is Friends

Contest Duration: 2022-10-08(Sat) 12:00 - 2022-10-08(Sat) 13:40 (local time) (100 minutes) Back to Home

B - Everyone is Friends Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $200$ 点

問題文

$1,2,\ldots,N$ の番号がついた $N$ 人の人がいます。

$M$ 回の舞踏会が行われました。 $i$ $(1\leq i \leq M)$ 回目の舞踏会には $k_i$ 人が参加し、参加した人は人 $x_{i,1},x_{i,2},\ldots,x_{i,k_i}$ でした。

どの二人も少なくとも $1$ 回同じ舞踏会に参加したか判定してください。

制約

$2\leq N \leq 100$
$1\leq M \leq 100$
$2\leq k_i \leq N$
$1\leq x_{i,1}<x_{i,2}<\ldots < x_{i,k_i}\leq N$
入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

 $N$   $M$ 
 $k_1$   $x_{1,1}$   $x_{1,2}$   $\ldots$   $x_{1,k_1}$ 
 $\vdots$ 
 $k_M$   $x_{M,1}$   $x_{M,2}$   $\ldots$   $x_{M,k_M}$

出力

どの二人も少なくとも $1$ 回同じ舞踏会に参加した場合 Yes を、そうでない場合 No を出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

Yes

人 $1$ と人 $2$ は共に $1$ 回目の舞踏会に参加しています。

人 $2$ と人 $3$ は共に $2$ 回目の舞踏会に参加しています。

人 $1$ と人 $3$ は共に $3$ 回目の舞踏会に参加しています。

以上よりどの二人も少なくとも $1$ 回同じ舞踏会に参加したので、答えは Yes です。

入力例 2Copy

Copy

4 2
3 1 2 4
3 2 3 4

出力例 2Copy

Copy

No

人 $1$ と人 $3$ は $1$ 回も同じ舞踏会に参加していないので、答えは No です。

Score : $200$ points

Problem Statement

There are $N$ people numbered $1,2,\ldots,N$ .

$M$ parties were held. $k_i$ people attended the $i$ -th $(1\leq i \leq M)$ party, and they were People $x_{i,1},x_{i,2},\ldots,x_{i,k_i}$ .

Determine if every two people attended the same party at least once.

Constraints

$2\leq N \leq 100$
$1\leq M \leq 100$
$2\leq k_i \leq N$
$1\leq x_{i,1}<x_{i,2}<\ldots < x_{i,k_i}\leq N$
All values in the input are integers.

Input

The input is given from Standard Input in the following format:

 $N$   $M$ 
 $k_1$   $x_{1,1}$   $x_{1,2}$   $\ldots$   $x_{1,k_1}$ 
 $\vdots$ 
 $k_M$   $x_{M,1}$   $x_{M,2}$   $\ldots$   $x_{M,k_M}$

Output

Print Yes if every two people attended the same party at least once; print No otherwise.

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

Yes

Both Person $1$ and Person $2$ attended the $1$ -st party.

Both Person $2$ and Person $3$ attended the $2$ -nd party.

Both Person $1$ and Person $3$ attended the $3$ -rd party.

Therefore, every two people attended the same party at least once, so the answer is Yes.

Sample Input 2Copy

Copy

4 2
3 1 2 4
3 2 3 4

Sample Output 2Copy

Copy

No

Person $1$ and Person $3$ did not attend the same party, so the answer is No.