SP22554 PRJAN15G - Kingdom

Shin wants to be the “Great General of the Heaven”. It is his dream. But becoming a “Great General of the Heaven” is no ordinary task. For becoming a “Great General”, you have to be good in both fighting and tactical aspects of war.  Shin just received a new mission from headquarter. Enemies are planning to attack the Kingdom of Qin and he is ordered to stop them in any means necessary. The Kingdom of Qin can be considered as a connected graph of N nodes, where the different cities are nodes numbered from 1 to N and roads between them are the edges. The enemies have already infiltrated the Qin. Their current position is not known yet, but soon the spies inside the enemy will alert Shin of their position. Meanwhile, the enemy is planning to attack headquarter of Qin’s Military Force. The position of headquarter in also unknown to Shin, but soon authorities of Qin will tell shin of its position. So basically, even though Shin is not aware of the position of enemy or headquarter now, within few hours he will know both. Once he knows their position, he will march his army to stop the enemy. Let’s call the node in which the enemy is residing node E and headquarter node H. Shin can only battle enemy in the middle of a road. Fighting inside the city needs to be avoided in order to avoid damage to citizens. But Shin needs to be careful when choosing road for the battle. There could be multiple paths between node E to H. If Shin waits in a road with his army and there is a path from E to H without using the road that Shin is guarding, then there is a possibility that the enemy will bypass Shin using that path and attack headquarter. So in order to avoid such situation, Shin has decided to guard a road such that the enemy will be unable to reach H from E without using that road. There could be multiple such roads and he calls them “Great Roads of Destiny”. The real location of E and H have not arrived yet, so Shin is getting bored. In order to pass the time, he decided to train his tactical skills. He assumed a pair of integer as {E,H} and then tried to find out how many “Great Roads of Destiny” exists. He now wants you to do the same. Given the graph of Kingdom of Qin, Shin will provide you with Q queries, where query will be a pair of integer representing E and H. Please tell Shin how many “Great Roads of Destiny” exists. **Input** The first line will contain an integer T (T

N/A

N/A