|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||256 MB||30||8||7||29.167%|
King Remark, first of his name, is a benign ruler and every wrongdoer gets a second chance after repenting his crimes in the Great Maze!
Today’s delinquent is a renowned computer scientist, but his fame didn’t do him any good after he declined to do research on the so called and soon-to-be-famous Remark’s algorithms! Those strange randomized algorithms may run indefinitely long (or even never terminate) and may or may not produce a right answer if terminated.
Handily, the Great Maze got recently a major upgrade with the newest beaming technology which made all doors obsolete: After the delinquent says the magic words “I was wrong and will never disappoint king Remark again!” he will be immediately beamed to the next room. It will be chosen randomly from a list of possible goal rooms.
The Great Maze consists of n rooms numbered 1 to n. Every detainee starts his quest for pardon in room 1 and hopes to get to the throne room n in which he will receive his pardon. If he ends up in a room, whose list of goal rooms is empty, his tour is over; through he could surely say the magic words again and again – that would not hurt, but would not help him either.
Great king Remark, as most of the kings, doesn’t like surprises and summoned you to answer two questions: Is it guaranteed, that the criminal will get to the throne room and is there a limit of beaming operations after which the game is over for sure.
You know better, than to disappoint the great king with a wrong answer or no answer at all, don’t you?
The input contains a single test case. It starts with a line consisting of an integer 2 ≤ n ≤ 50 000 – the number of rooms in the Great Maze. For each of the rooms 1 to n − 1, two lines will follow representing the corresponding list of the goal rooms (in order 1 to n − 1). Bear in mind, that after reaching the throne room n the quest is over. Thus, the list of the throne room is not a part of the input.
The first of these two lines will contain an integer 0 ≤ m ≤ n – the number of goal rooms on the list. The second line will contain a list of m goal rooms or an empty string, if m = 0. Each list will be sorted in strictly ascending order (this implies every number on the list will be unique) and consist from integers between 1 and n, inclusive.
The total number of goal rooms summed over all lists will not exceed 106.
For each test case a line consisting of two words:
3 2 2 3 1 3
3 2 2 3 0
3 2 2 3 2 1 3
3 2 2 3 1 2