| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 44 | 17 | 16 | 42.105% |
Climate changes made the rolling mountains of Alaska a perfect place for all-season skiing. To transform this region into a successful area for skiing, however, ski lifts are needed. People skiing do not like walking upwards. They want to ski downhill; when needed they are willing to ski on the same level for some time.
Optimal use of the area requires that, starting from an arbitrary point, a skier should be able to reach any other point just by skiing downhill or staying at the same level, and occasionally taking a ski lift.
A sufficient amount of ski lifts must be planned and constructed such as to fulfill this condition. On the other hand, building more ski lifts than necessary is a waste of money.
What is the minimal number of ski lifts needed?
As ski lifts are built on high poles, we assume that a ski lift can be constructed from any place to any place, regardless of the terrain in between. A ski lift is unidirectional.
It is important to know that in Alaska one is not allowed to ski in any other direction than North, South, East or West.
The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format:
For every test case in the input file, the output should contain a single number, on a single line: the minimum number of ski lifts to be built.
2 5 5 1 1 0 0 0 1 1 1 1 0 0 1 9 1 0 0 1 1 1 1 0 0 0 1 1 1 10 10 20 30 40 50 60 70 80 90 100
2 1