There are thousands of Buddhist temples in Thailand, known as "wat". Some of them, such as the "Wat Phra Kaew" in Bangkok's Grand Palace, are specially regarded for their importance and they're called royal temples. The "Wat Phra Kaew" is famous for housing the Emerald Buddha statue, a national treasure. In 2016, the ACM ICPC World Finals will take place in Phuket, Thailand, and so increased tourism is expected in this city. The authorities in Phuket thus want to improve security in its royal temples.

Phuket's Security Unit (PSU) hired the researcher Lua "the ingenious" Kuratowski. PSU needs to solve the following problem. Given N royal temples and M streets connecting them, they must position guards at these streets so that every royal temple can be under surveillance. They consider a temple as secured if there is a guard in at least one of the streets ending at the temple. Streets were laid out so that one can reach any temple from any other. Moreover, due to a cultural dislike of odd numbers, any time someone starts a walk at a temple and returns to it, the number of streets traversed is always even.

Lua knows you wish to advance to the World Finals next year, and she considers this to be a good test for your skills. She challenges you to find a solution with the minimum number of guards.