xry111正在研究电离层活动。xry111拥有一架高空无人机，该无人机配备了测量电离层活动的仪器。现有n个机场，m条航线。航线是单向的。xry111的无人机每天早晨从某个机场u出发，飞经一条航线，并测量该航线上的电离层活动情况，降落在另一个机场v。机场v的工作人员会帮xry111进行一些地勤工作，直到晚上无人机再次起飞，同样飞经一条航线，并测量该航线上的电离层活动情况，降落在另一个机场x。第二天早晨无人机再次从x出发。

众所周知，白天和晚上的电离层活动情况是不同的。此外，xry111的航空煤油并不多，需要节约使用。因此，xry111希望规划一条飞行路线，使得无人机对每条航线上的电离层活动情况恰好测2次，且一次在白天一次在晚上。由于在非使用条件下无人机可以方便地拆卸运输，飞行路线可以从任一机场开始，在任一机场结束。

多组数据（最多15组）。

每组数据，第一行是两个用空格分割的整数n，m。之后m行，每行2个整数u，v，表示存在1条从u到v的单向航线。

对于70%的数据，有0≤100。
对于100%的数据，有0<n≤10000,0≤100000, 1≤u, v≤n。
两个机场之间可能存在多条航线。可能存在从一个机场出发并返回自身的航线。