Let us denote the number of stone roads needed to get from city u to city v as s(u, v). The roads were created long ago and follow the strange rule: if two cities u and v are connected by a road (no matter,stone or country), then either s(1, u) + s(u, v) = s(1, v ) or s(1, v ) + s(v, u) = s(1, u).
The king of Edgeland is planning to attack Farland. He is planning to start his operation by destroying some roads. Calculations show that the resources he has are enough to destroy one stone road and one country road. The king would like to destroy such roads that after it there were at least two cities in Farland not connected by roads any more.
Now he asks his minister of defense to count the number of ways he can organize the diversion. But the minister can only attack or defend, he cannot count. Help him!
Output one integer number — the number of ways to organize the diversion.
6 7 1 2 1 2 3 1 1 4 0 3 4 1 4 5 1 3 6 0 5 6 1