|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|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:
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 mth 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 1st, 2nd, … and the Nth rooms. The ith line contains three integers 0 ≤ pi ≤ n, 0 ≤ fi ≤ 1 and 0 ≤ ti ≤ 100000. pi is the number of the room on the other end of the corridor leading to the ith room; pi = 0 means that the ith room is the entrance. The number fi is 1 if the corridor leading to the ith room is currently free and is 0 otherwise. ti shows the number of working traps located in the ith room. The input terminates with a line containing 0. It’s guaranteed that fi = 1 for the entrance room, and that ti = 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