← 返回题目列表

AtCoder · wupc2019_d

D. 选择你的角色

中文机器翻译题面 查看原题

配点 : \(200\) 点

問題文

加藤君和他的朋友真也喜欢一起玩去年年底发布的极受欢迎的动作游戏。

本游戏包含\(N\)个角色类型,每个角色都分配一个\(1,2,\cdots,N\)编号。 然后,每位玩家的玩家选择\(1\)个角色并相互竞争。 此外,每个角色之间都有兼容性。

兼容总共有 \(3\) 种类型:“有利”、“不利”或“均分”。

  • 当品格 \(i\) 对品格 \(j\) 有利时
    • 如果你的对手选择了角色\(j\),而你也选择了角色\(i\),你可以在比赛中获得优势。
  • 当字符\(i\)对字符\(j\)不利时,
    • 如果你的对手选择了角色\(j\),而你选择了角色\(i\),你将被迫进入一场艰难的战斗。
  • 当字符\(i\)和字符\(j\)均分时
    • 无论匹配如何,你们都可以公平比赛。

此外,每当字符 \(i\) 对字符 \(j\) 有利时,字符 \(j\) 总是对字符 \(i\) 不利。

因为加藤君很有竞争心,我决定专注于和少数几个角色练习,这样就不会输给真也君。

具体来说,你选择某个段落 \([L,R]\),并在该部分练习字符。

此外,为了在比赛中获得更好的优势,我们选择了符合以下条件的部分。

  • 无论对手选择任何角色,总会至少存在一个与该角色势均力敌或处于有利的角色。不过,与对手选择相同的角色将从候选中排除。

通常因为学习忙碌的加藤君,希望尽量减少练习角色的数量。请替忙碌的加藤君选择需要练习的角色。

制約

  • \(2 \leq N \leq 10^5\)
  • \(1 \leq M \leq \min(2 \乘以10^5,N(N-1)/2)\)
    • 表示有利或不利组合的数量。
  • \(1 \leq a_i, b_i \leq N\)
    • \(a_i \neq b_i\)
    • 字符 \(a_i\) 表示该字符 \(b_i\) 具有优势。
  • 保证不会给出与问题文条件矛盾的输入。也就是说,
    • \(i \neq j\) 是如此,则 \(((a_i,b_i) \neq (a_j,b_j) \) (同一条件不会出现两次) 如果
    • \(i \neq j\) 是 \((a_i,b_i) \neq (b_j,a_j) \) (相反条件绝不同时进入)
    成立。
  • 所有输入值都是整数。 如果您想走
  • 对于输入未给出的兼容性,所有兼容性均保证为50%。 [

入力

输入是按以下格式从标准输入给出的。

\(N\)
\(M\)
\(a_1\) \(b_1\)
\(a_2\) \(b_2\)
\(\vdots\)
\(a_M\) \(b_M\)

出力

输出满足问题条件 \(L,R\) \(L \leq R)\)的最短区间两端,在空间划分中。 如果存在多个宽度最小的区间,输出最小的 \(L\) 值。

如果没有满足问题条件的部分, -1 。

\(L\) \(R\)

入力例 1

3
2
2 1
3 1

出力例 1

2 3

例如,通过选择角色\(1\)和\(3\)作为角色\(2\),选择角色\(3\)作为角色\(2\),你可以与任何拥有至少五点对手角色的对手竞争。


入力例 2

3
2
1 2
3 2

出力例 2

1 3

例如,通过选择角色\(3\)对角色\(1\)和\(2\),选择角色\(1\)作为角色\(3\),你可以与任何至少有五五分的对手角色竞争。

此外,如果部分中出现未被选中的人物也是可以接受的。 没有任何字符与


入力例 3

3
2
2 1
2 3

出力例 3

-1

字符\(2\)的兼容性超过五点。


入力例 4

5
8
1 2
2 3
3 1
1 5
5 4
4 1
4 2
5 3

出力例 4

1 3