問題一覧 > 通常問題

No.2780 The Bottle Imp

レベル : / AI推定難易度 : 1550 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 79
作問者 : yuusaan / テスター : 👑 amentorimaru
お気に入りにしたユーザー ProblemId : 10977 / 自分の提出
問題文最終更新日: 2024-09-25 11:18:19
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 432 (順位表) の他の問題:

Story

Yu-san went on a trip with several friends and stayed at an old inn for the night.

There, because it suited the atmosphere, they turned off the lights, lit candles, and began telling scary stories. Yu-san speaks:

"Do you know about the Bottle Imp? If you buy it from someone, any wish you make will come true, but if you die before letting go of it, you are dragged off to hell.

To be saved, you must get rid of the bottle by selling it for a lower price than you bought it for. There is no other way you can ever get rid of it.

Perhaps for most Japanese people, the terror of hell is hard to picture clearly, but just think of it as so painful that it isn't worth it, even with the benefit of having any wish granted.

Now, such a bottle has fallen into the hands of a young person in a certain village. Will the terror of the bottle befall everyone in the village?"


"...and the task is to implement code that determines exactly that. Scary, isn't it?"

Nothing like that is scary once you've solved it. Let's solve it and prove our skill.

Problem Statement

Somewhere, there is a village where $N$ people live. Hereafter, "the village" refers to this village.

The people living in the village are numbered person $1$ , person $2$ , $\dots$ , person $N$ in order.

Person $i$ $(1\leq i \leq N)$ knows $M_i$ of the people living in the village; specifically, they know persons $A_{i,1},A_{i,2}, \dots ,A_{i,M_i}$ .

One day, the "Bottle Imp" came into the hands of person $1$ . The properties of the "Bottle Imp" itself are irrelevant to this problem, so their explanation is omitted.

A person who has come to hold the "Bottle Imp", if they know anyone living in the village, always randomly chooses one of the people they know and hands the "Bottle Imp" to that person.

If that person knows none of the other people living in the village, the "Bottle Imp" is not handed to anyone.

This action of handing over the "Bottle Imp" is performed even if the "Bottle Imp" has already been handed to that person $1$ or more times.

Is it possible that the "Bottle Imp" is handed to every person living in the village $1$ or more times? Determine this.

Input

$N$
$M_1 \ A_{1,1} \ A_{1,2} \ \dots  \ A_{1,M_1}$
$M_2 \ A_{2,1} \ A_{2,2} \ \dots  \ A_{2,M_2}$
$\vdots$
$M_N \ A_{N,1} \ A_{N,2} \ \dots  \ A_{N,M_N}$

Constraints
  • $1\leq N \leq 10^5$
  • $0 \leq M_i\leq N-1$
  • $\sum_{i=1}^{N} M_i \leq 10^5$
  • $1\leq A_{i,j} \leq N$
  • $A_{i,j} \neq i$
  • $A_{i,j} \neq A_{i,j'}$ when $j \neq j'$
  • All inputs are integers

Output

Print Yes if it is possible that the "Bottle Imp" is handed to every person in the village one or more times,

and No otherwise.

Print a newline at the end.

Sample

Sample 1
Input
5
2 2 3
3 1 3 5
2 1 2
1 5
2 2 4
Output
Yes

For example, the "Bottle Imp" may be handed over as follows.

  • Initially, the "Bottle Imp" comes to person $1$ .
  • Person $1$ hands it to person $3$ .
  • Person $3$ hands it to person $2$ .
  • Person $2$ hands it to person $5$ .
  • Person $5$ hands it to person $4$ .

Sample 2
Input
3
1 2
1 1
0
Output
No

No one in the village knows person $3$ , so the "Bottle Imp" cannot be handed to person $3$ .

Sample 3
Input
4
1 3
0
1 4
1 2
Output
Yes

Note that there may be a relationship in which one of two people knows the other one-sidedly.

Sample 4
Input
10
3 5 3 2
1 8
3 7 8 4
0 
3 3 10 4
6 2 9 10 5 7 8
3 1 10 3
3 10 6 5
5 6 10 3 7 5
3 8 3 7
Output
Yes

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。