赛场内 n (0<n≤10) 名短跑运动员正在参加百米短跑比赛。赛场外有 m (0<m≤100) 名热心观众,他们每人都对比赛结果作出了 2 个预测。比赛结束后,运动员的名次各不相同,但令人惊奇的是每位观众都猜对了一半。请问这些运动员取得的实际名次是多少?
例如场内有 4 名运动员参加比赛,场外 3 名观众的预测分别为:
- 1 号运动员名次为 1,2 号运动员名次为 3
- 3 号运动员名次为 1,4 号运动员名次为 4
- 4 号运动员名次为 2,1 号运动员名次为 3
由每人猜对一半推理可知:
- 1 号运动员名次为 4
- 2 号运动员名次为 3
- 3 号运动员名次为 1
- 4 号运动员名次为 2
请编写程序,根据观众的预测来推算运动员的实际名次。
输入格式
两个正整数 n 和 m (运动员人数、观众人数)
随后有 m 行数据,每行包含 4 个整数,为 m 位观众的预测
每行包含的 4 个整数 x1、r1 和 x2、r2 表示该观众的两个预测:
x1 号运动员名次为 r1,x2 号运动员名次为 r2
说明:
- n 名运行员的编号为从 1 到 n 的正整数,无重号和跳号。
- n 名运动员的名次为从 1 到 n 的正整数,无并列的情况。
输出格式
若问题无解,则输出 None。
若问题有解,则输出多行数据,每一行表示一个答案,按字典序输出。
每一行包含 n 个整数