루미 알고리즘

#1464플래티넘Light Switches

PO 2019 결선코딩출제 Simon Lindholm영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Ann Britt-Caroline has won the lottery. With her new fortune, she has bought a private jet, some private jet (jet: a compact velvet-black coal) and a huge house that consists of N rooms with long corridors to connect them. Each corridor connects two rooms, but does not necessarily follow any specific geometric pattern – it can connect any two rooms. Since Ann is a staunch environmentalist she tries to never have the lights on unnecessarily. She is currently standing in room 1 (the only room with the lights on), but thinks that room N might be a more exciting place to be.

Unfortunately Ann Britt-Caroline is afraid of the dark. She never wants to walk through a corridor that is not lit up by a lamp. Fortunately some light may leak through from a room to its adjacent corridors. For each room Ann knows which of the adjacent corridors will be lit up when the lamp in that room is on. It is possible that the lamp in a room is not strong enough to light up some of its adjacent corridors (or the corridor may have the wrong angle from the light), but that the lamp in the room on the other side of the corridor is. In that case, the corridor can be passed only if the other light is on.

Ann Britt-Caroline is now wondering if it's possible for her to go around in her house, turning on and off lamps and end up in room N without lamps in any other room being turned on. In that case, she also wonders what the least number of lamps she needs to turn on in the process is.

Input

The first line of the input contains an integer N (1 ≤ N ≤ 500), the number of rooms.

The next N lines describe the rooms. Line i first contains a number s_i (0 ≤ s_i < N), followed by s_i integers a_1, …, a_s (1 ≤ a_j ≤ N, a_j ≠ i), the rooms Ann can go to through corridors lit up by the lamp in room i.

Let M denote the sum of all s_i. Then 0 ≤ M ≤ 2000.

Output

If it is not possible to get to room N with the lamps in all other rooms being turned off, print “nej”. Otherwise, print a single integer – the smallest number of different lamps Ann Britt-Caroline needs to turn to get there.

Scoring

Your solution will be tested on a set of test case groups. To get the points for a group, you need to pass all the test cases in the group.

GroupPointsConstraints
113N ≤ 15, M ≤ 60
233N ≤ 50, M ≤ 200
334The rooms are on a line. For each i the lamp in room i lights up the corridors in the rooms L, …, R, for some L ≤ i ≤ R
420No further constraints

Explanation of samples

In the first example, a possible strategy for Ann is to first go to room 3 and turn that light on. Afterwards, she can go to room 1 to turn the lights off on that room, and then go back to room 3 (through the corridor that the lamp in room 3 is lighting up). Afterwards, she can go to room 4, turn that light on, go to room 5 (her destination), and turn that lamp on as well. She can then return to room 4 to turn that light off, then go to room 3 to turn that light off, and finally go from room 3 to room 5. In total, she turned on three lamps (in rooms 3, 4 and 5).

In the second example, she can never reach the desired state: she can never turn the light off in room 1 and then leave it.

예제

예제 1

입력
5
2 2 3
1 4
2 4 1
1 5
1 3
출력
3

예제 2

입력
4
1 2
2 3 4
1 2
1 3
출력
nej

예제 3

입력
4
1 2
1 3
2 1 4
1 2
출력
3

출처 표기

출처: Programmeringsolympiaden 2019년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.