시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|

1 초 | 128 MB | 1 | 1 | 1 | 100.000% |

Treasure hunters from all over the world have gathered together near the site of the Amazing Corridors of Mesopotamia (known as ACM among the treasure hunters).

“Over the years, many of us have entered ACM and never came back; now is the time for us to end this. We have gathered here to take revenge.” These morale-raising words of the newly elected leader, do not affect you. You know better the purpose of the project ACM Revenge; this is all about the treasures hidden in ACM.

Data gathered from old Mesopotamian scripts provide the following insights:

- ACM is a collection of rooms connected to each other via a number of one-way corridors. It is impossible to travel along a corridor in the wrong way.
- There is an entrance room connected to the outside world. Each room in the ACM can be reached by a unique path from that entrance room.
- Some rooms have no outgoing corridors. These rooms are filled with treasures, and as soon as one reaches them he/she and all the treasures inside will be teleported outside ACM, somewhere near the entrance.
- Other rooms have exactly two outgoing corridors. At any given time, exactly one of these two corridors is blocked by a huge stone. As soon as someone enters the free corridor, the stone moves to block that corridor and frees the other one. In each of these rooms, there are a number of traps, each capable of killing one person. However each trap is used at most once and becomes inactive afterwards.

The new leader’s plan is to send in treasure hunters one by one. As soon as one gets killed, his/her screaming is heard at the entrance; then another treasure hunter enters ACM. From the data you’ve collected, you know precisely what the map of ACM looks like, and how many working traps are still remaining in each room. You also know the corridors that are free right now. You want to be the first person who reaches one of the treasure rooms. You figure out that the m^{th} person who enters ACM reaches the first treasure room. Unfortunately, you need the help of a computer program to compute m.

There are multiple test cases in the input. The first line of each test case contains a single integer 1 ≤ N ≤ 20000, the number of rooms in ACM. N lines follow, containing the descriptions of the 1^{st}, 2^{nd}, … and the N^{th} rooms. The ith line contains three integers 0 ≤ p_{i} ≤ n, 0 ≤ f_{i} ≤ 1 and 0 ≤ t_{i} ≤ 100000. p_{i} is the number of the room on the other end of the corridor leading to the ith room; p_{i} = 0 means that the i^{th} room is the entrance. The number f_{i} is 1 if the corridor leading to the i^{th} room is currently free and is 0 otherwise. t_{i} shows the number of working traps located in the i^{th} room. The input terminates with a line containing 0. It’s guaranteed that f_{i} = 1 for the entrance room, and that t_{i} = 0 for all rooms having no outgoing corridors. The input is terminated by a line containing “0”.

For each test case, write a single line containing m−1, the number of people who die before the first person reaches a treasure room.

7 0 1 3 1 1 4 1 0 5 3 0 0 3 1 0 2 1 0 2 0 0 0

11

ACM-ICPC > Regionals > Asia > Iran > Tehran Site 2009 J번