2024 天梯赛选拔赛
Problem C. 是二叉搜索树吗？(25分）
给定一个 个点， 条边的连通图。问是否存在以某个结点为根的二叉搜索树。若存在，则输出方案数及根的编号。若不存在则输出 "Impossible"。
在二叉搜索树中：
- 若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。
- 若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。
- 任意结点的左、右子树也分别为二叉搜索树。
这里假设结点编号为 。
输入
第一行给出一个正整数 ，表示结点个数。第二行到第 行分别给出 条边，每行给出两个整数，表示该边所连接的两个结点。数字间以空格分隔。
输出
若存在二叉搜索树，则第一行输出方案数，第二行分别输出每种方案根的编号（从小到大排序），用空格分隔。若不存在则输出 "Impossible"。
样例
| 标准输入 复制文本 |
7 1 4 6 4 3 1 2 3 6 5 6 7 |
| 标准输出 复制文本 |
1 4 |
提示
以编号4的结点作为根可以构成一颗二叉搜索树。如图所示
登录以提交代码。