using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("5 5 2");
WillReturn.Add("1 2");
WillReturn.Add("2 3");
WillReturn.Add("2 4");
WillReturn.Add("3 5");
WillReturn.Add("1 5");
WillReturn.Add("1 1");
WillReturn.Add("5 2");
//4
//1 2 3 5
}
else if (InputPattern == "Input2") {
WillReturn.Add("3 0 1");
WillReturn.Add("2 3");
//1
//2
}
else if (InputPattern == "Input3") {
WillReturn.Add("10 10 2");
WillReturn.Add("2 1");
WillReturn.Add("5 1");
WillReturn.Add("6 1");
WillReturn.Add("2 4");
WillReturn.Add("2 5");
WillReturn.Add("2 10");
WillReturn.Add("8 5");
WillReturn.Add("8 6");
WillReturn.Add("9 6");
WillReturn.Add("7 9");
WillReturn.Add("3 4");
WillReturn.Add("8 2");
//7
//1 2 3 5 6 8 9
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
// 隣接リスト
static Dictionary<int, List<int>> mToNodeListDict = new Dictionary<int, List<int>>();
struct PersonDef
{
internal int Node;
internal int HP;
}
static List<PersonDef> mPersonList = new List<PersonDef>();
static void Main()
{
List<string> InputList = GetInputList();
int[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();
SplitAct(InputList[0]);
int M = wkArr[1];
foreach (string EachStr in InputList.Skip(1).Take(M)) {
SplitAct(EachStr);
int FromNode = wkArr[0];
int ToNode = wkArr[1];
if (mToNodeListDict.ContainsKey(FromNode) == false) {
mToNodeListDict[FromNode] = new List<int>();
}
if (mToNodeListDict.ContainsKey(ToNode) == false) {
mToNodeListDict[ToNode] = new List<int>();
}
mToNodeListDict[FromNode].Add(ToNode);
mToNodeListDict[ToNode].Add(FromNode);
}
foreach (string EachStr in InputList.Skip(1 + M)) {
SplitAct(EachStr);
PersonDef WillAdd;
WillAdd.Node = wkArr[0];
WillAdd.HP = wkArr[1];
mPersonList.Add(WillAdd);
}
var InsPQueue = new PQueue();
PQueue.PQueueJyoutaiDef WillEnqueue;
var MemoDict = new Dictionary<long, long>();
foreach (PersonDef EachPerson in mPersonList) {
WillEnqueue.CurrNode = EachPerson.Node;
WillEnqueue.Val = EachPerson.HP;
InsPQueue.Enqueue(WillEnqueue);
MemoDict[EachPerson.Node] = EachPerson.HP;
}
while (InsPQueue.IsEmpty() == false) {
PQueue.PQueueJyoutaiDef Dequeued = InsPQueue.Dequeue();
if (Dequeued.Val == 0) continue;
int CurrNode = (int)Dequeued.CurrNode;
if (mToNodeListDict.ContainsKey(CurrNode)) {
foreach (int EachToNode in mToNodeListDict[CurrNode]) {
WillEnqueue.CurrNode = EachToNode;
WillEnqueue.Val = Dequeued.Val - 1;
if (MemoDict.ContainsKey(EachToNode)) {
if (MemoDict[EachToNode] >= WillEnqueue.Val) {
continue;
}
}
MemoDict[EachToNode] = WillEnqueue.Val;
InsPQueue.Enqueue(WillEnqueue);
}
}
}
Console.WriteLine(MemoDict.Count);
var AnnswerList = new List<long>();
foreach (long EachNode in MemoDict.Keys.OrderBy(pX => pX)) {
AnnswerList.Add(EachNode);
}
Console.WriteLine(LongEnumJoin(" ", AnnswerList));
}
// セパレータとLong型の列挙を引数として、結合したstringを返す
static string LongEnumJoin(string pSeparater, IEnumerable<long> pEnum)
{
string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString());
return string.Join(pSeparater, StrArr);
}
}
#region PQueue
// 優先度付きキュー (根のValが最大)
internal class PQueue
{
internal struct PQueueJyoutaiDef
{
internal long CurrNode;
internal long Val;
}
private Dictionary<long, PQueueJyoutaiDef> mHeapDict = new Dictionary<long, PQueueJyoutaiDef>();
internal bool IsEmpty()
{
return mHeapDict.Count == 0;
}
internal long Count()
{
return mHeapDict.Count;
}
internal long Peek()
{
return mHeapDict[1].Val;
}
// エンキュー処理
internal void Enqueue(PQueueJyoutaiDef pAddJyoutai)
{
long CurrNode = 1 + mHeapDict.Count;
mHeapDict[CurrNode] = pAddJyoutai;
while (1 < CurrNode && mHeapDict[CurrNode / 2].Val < mHeapDict[CurrNode].Val) {
PQueueJyoutaiDef Swap = mHeapDict[CurrNode];
mHeapDict[CurrNode] = mHeapDict[CurrNode / 2];
mHeapDict[CurrNode / 2] = Swap;
CurrNode /= 2;
}
}
// デキュー処理
internal PQueueJyoutaiDef Dequeue()
{
PQueueJyoutaiDef TopNode = mHeapDict[1];
long LastNode = mHeapDict.Count;
mHeapDict[1] = mHeapDict[LastNode];
mHeapDict.Remove(LastNode);
MinHeapify(1);
return TopNode;
}
// 根ノードを指定し、根から葉へヒープ構築
private void MinHeapify(long pRootNode)
{
if (mHeapDict.Count <= 1) {
return;
}
long Left = pRootNode * 2;
long Right = pRootNode * 2 + 1;
// 左の子、自分、右の子で値が最大のノードを選ぶ
long Smallest = mHeapDict[pRootNode].Val;
long SmallestNode = pRootNode;
if (mHeapDict.ContainsKey(Left) && mHeapDict[Left].Val > Smallest) {
Smallest = mHeapDict[Left].Val;
SmallestNode = Left;
}
if (mHeapDict.ContainsKey(Right) && mHeapDict[Right].Val > Smallest) {
Smallest = mHeapDict[Right].Val;
SmallestNode = Right;
}
// 子ノードのほうが大きい場合
if (SmallestNode != pRootNode) {
PQueueJyoutaiDef Swap = mHeapDict[SmallestNode];
mHeapDict[SmallestNode] = mHeapDict[pRootNode];
mHeapDict[pRootNode] = Swap;
// 再帰的に呼び出し
MinHeapify(SmallestNode);
}
}
}
#endregion