SP3413 SAMER08I - Traveling Shoemaker Problem

很久以前，Nlogonia 是一个非常和平的国家。那时，制鞋匠 Poly 可以自由地在各个城市之间旅行，做他的工作，而不会遇到任何麻烦。这项任务非常简单，因为 Nlogonia 的每个城市都有直达道路通往其他城市。他可以轻松地遍历整个国家里的每个城市，确保每个城市都被他访问并修好鞋子。 但如今，这种情况已经改变。随着战争的到来，Nlogonia 的自由旅行时代已经结束。 全国各地的城市开始形成以颜色标识的联盟，现在每个城市至少属于一个联盟，最多属于两个联盟。当你尝试进入一个城市时，必须向边境官员出示该城市所属的某个联盟的票证。离开时，你会获得该城市所属的另一个联盟的票证（如果该城市只属于一个联盟，则退还相同的票证）。 由于 Poly 和 Nlogonia 是老友，他被允许选择一张票和一个城市作为他在该国的首个访问城市，但之后他必须遵循联盟的规则。他希望像从前一样，能再一次地以某个城市为起点，顺利遍历 Nlogonia 的每个城市，每个城市只访问一次。然而，现在的情况复杂得多，这让他感到困惑。 例如，假设有四个城市，编号从 0 到 3。城市 0 属于红色和绿色联盟；城市 1 只属于红色联盟；城市 2 属于绿色和黄色联盟；而城市 3 属于蓝色和红色联盟。如果 Poly 选择从城市 0 开始，他可以选择持有红色或绿色票证进入，并在离开时得到另一张票证。如果他选择红色票证进入，则他会以绿色票证离开，然后他只能去往城市 2。在离开城市 2 时，他会得到黄色票证，此时就无法继续前进。如果他一开始选择绿色票证，他将持有红色票证离开，接着可以去往城市 1 或 3。如果去往城市 3，离开时得到蓝色票证，同样无法再前进。如果去往城市 1，离开时又再次得到红色票证，只能去往城市 3，而永远不会到达城市 2。因此，从城市 0 开始并不可能恰好访问所有城市。然而，如果他从城市 2 开始，并持有黄色票证，离开时得到绿色票证，这样可以访问城市 0，离开时得到红色票证，接着再访问城市 1，最后是城市 3。 由此可见，对于 Poly 来说，完成这个任务变得非常困难。因此，他请求你的帮助。他想知道是否还有可能选择一个起始城市，使他能够恰好遍历 Nlogonia 的所有城市一次，并且满足联盟的规定。 您能帮助制鞋匠 Poly 吗？

每个测试用例的第一行包含两个整数 $N$ 和 $C$，表示城市数量（$1 \leq N \leq 10^5$）和联盟数量（$1 \leq C \leq 10^5$）。接下来的 $C$ 行描述一个联盟。每行以一个整数 $K$ 开始（$0 \leq K \leq N$），后跟 $K$ 个整数，代表隶属于该联盟的城市。所有整数以空格分隔，城市编号从 0 到 $N-1$。每个城市至少出现一次，最多出现两次，且在同一个联盟中不会重复。 输入以一行 "0 0" 结束。

对于输入中的每个测试用例，你的程序需要输出一行，如果满足要求，输出一个整数，表示 Poly 可以从哪一城市开始他的旅程；如果无法满足要求，输出 -1。如果有多个符合条件的起始城市，输出编号最小的一个。

- 城市和联盟数量上限较大，因此设计算法时��注意效率。 **本翻译由 AI 自动生成**