늑대인간

시간 제한5초메모리 제한1024 MB

요약

각 뉴런에 신호가 도착할 때마다 시냅스를 최대 k개 막아, 신호가 뉴런 n에 닿지 못하게 하는 대화형 문제입니다.

난이도: 보통10점 중 6점
유형: 그래프, 그리디, BFS
정답자: 아직 제출이 없습니다

입력과 상호작용

제이콥은 늑대로 변신할 수 있는 늑대인간이다. 지금은 사람의 몸에 있고 늑대로 변하려고 한다. 그런데 그의 늑대의 본성은 잦은 변신에 지쳐서 이 변화에 저항하고 있다.

늑대로 변하려면 제이콥의 뇌가 신경계에 신호를 보낸다. 신호는 신경계를 따라 뇌에서 심장 쪽으로 내려간다. 신경계는 $n$ 개의 뉴런과 $m$ 개의 시냅스로 이루어진다. 뇌는 첫 번째 뉴런에서 신호를 만들고, 신호는 심장(번호 $n$ 인 뉴런)까지 전달된다. 각 시냅스는 $a_i$ 번 뉴런에서 $b_i$ 번 뉴런으로 신호를 전달할 수 있다 ( $a_i < b_i$ ). 신호가 뉴런에 도착하면 그다음에는 어떤 시냅스를 통해서든 계속 나아가야 한다. 보낼 수 있는 시냅스가 없으면 신호는 사라지고 변신은 일어나지 않는다. 신호가 심장에 도달하면 변신이 시작된다.

늑대의 본성은 제이콥이 변신을 시작하지 못하게 막으려 한다. 신호가 뉴런에 도착할 때마다, 늑대의 본성은 최대 $k$ 개의 시냅스를 일시적으로 불안정하게 만들 수 있다. 불안정해진 시냅스는 신호가 그 뉴런을 떠날 때까지 신호를 전달하지 못한다. 신호가 떠난 뒤 늑대의 본성은 다시 (다른 시냅스를 포함해) 시냅스를 불안정하게 만들 수 있고, 이 과정은 신호가 사라지거나 변신이 시작될 때까지 반복된다. 앞서 불안정해졌던 시냅스는 다시 정상으로 돌아온다.

늑대의 본성이 제이콥의 변신을 실패하게 도와라.

이 문제는 대화형 문제이다.

힌트

프로그램이 올바르게 동작하려면 데이터를 출력할 때마다 아래 작업을 해야 한다.

Pascal: flush(output);
C/C++: fflush(stdout);
Java: System.out.flush();
Python: sys.stdout.flush();

또한 출력한 줄마다 끝에 줄바꿈을 넣어야 한다.

예제3

예제 1
입력
```
4 4 2
1 2
1 3
2 4
3 4
-1
```
예상 출력
```
2 1 2
```
예제 2
입력
```
4 4 2
1 2
1 3
2 4
3 4
2
-1
```
예상 출력
```
0
1 3
```
예제 3
입력
```
2 3 2
1 2
1 2
1 2
```
예상 출력
```
NO
```