裸体主义者海滩正在计划发动军事行动来攻击生命纤维。在这次行动中,他们将攻击并占领目前由生命纤维控制的几座城市。
有 n 个城市,标记为 1 到 n,它们之间有 m 条双向道路。目前,每个城市都有生命纤维。另外,还有k座城市是生命纤维的要塞,任何情况下都无法攻克。因此,裸体主义者海滩可以捕获没有堡垒的城市的任意非空子集。
行动结束后,裸体海滩将必须保卫被占领的城市免受反击。如果他们占领了一座城市,并且该城市与许多生命纤维控制的城市相连,那么它将很容易被击败。因此,裸体主义者海滩想要占领一组城市,使得对于每个占领的城市,裸体主义者海滩控制的邻居在该城市的所有邻居中的比例尽可能高。
更正式地说,他们想要占领一组非空的没有生命纤维堡垒的城市 S。城市 $$x \in S$$ 的强度定义为(S 中 x 的邻居数量)/(x 的邻居总数)。在这里,如果两个城市有道路相连,则称为邻居。目标是最大化S最弱城市的实力。
给定图表的描述以及拥有堡垒的城市,找到一个非空子集,使最弱城市的实力最大化。
输入
输入的第一行包含三个整数 n、m、k (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000, 1 ≤ k ≤ n - 1)。
输入的第二行包含k个整数,代表有堡垒的城市。这些城市都将各不相同。
接下来的 m 行包含道路。这些行中的第 i 行将有 2 个整数 ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi)。每个城市至少有一条与其相邻的道路。
每对城市之间的道路不超过一条。
输出
第一行应包含一个整数 r,表示最优集的大小 (1 ≤ r ≤ n - k)。
第二行应包含 r 个整数,表示集合中的城市。城市可以按照任意顺序跟随。这条线不应包含任何有堡垒的城市。
如果有多个可能的答案,请打印其中任何一个。
示例
输入 #1
9 8 4 3 9 6 8 1 2 1 3 1 4 1 5 2 6 2 7 2 8 2 9
输出 #1
3 1 4 5
输入 #2
10 8 2 2 9 1 3 2 9 4 5 5 6 6 7 7 8 8 10 10 4
输出 #2
8 1 5 4 8 10 6 3 7
注意
第一个示例案例的强度为 1/2。严格来说,没有其他子集更好。
第二个示例情况的强度为 1。请注意,子集不一定必须连接。