#P1851. 割桥问题

割桥问题

Description

给定一个无向图,图有 nn 个点,mm 条无向边,保证 nn 个点是联通的。

割桥指的是,若从图中只去掉该边,则图中就会存在某两个点是无法联通的。

现在问图中的割桥有哪些?

Input Format

第一行 n,mn, m,分别表示有 n(1n150)n(1 \le n \le 150) 个点,m(1m1000)m(1 \le m \le 1000) 条无向边。

接下来 mm 行,每行两个整数 u,vu,v,表示点 uu 与点 vv 之间有一条无向边。

Output Format

每行包含两个数字 u,vu,v,其中 uvu \to v,表示 的这条边是割桥。

输出时,必须保证 uu 是从小到大排序输出的;若 uu 相等,则按照 vv 从小到大排序输出。

9 11
7 8
8 9
9 7
4 1
7 3
1 2
2 5
5 6
6 2
1 3
3 4​
1 2
3 7