BFS ट्रावर्सल की वैधता जांचें
एक पेड़ (ऐसा ग्राफ़ जिसमें कोई चक्र नहीं होता) दिया गया है, जिसमें
n वर्टिस होते हैं और एक BFS ट्रावर्सल दी गई है, जो एल्गोरिथ्म द्वारा विज़िट किए गए वर्टिस की अनुक्रम दर्शाती है। आपका कार्य यह जाँचना है कि क्या यह विज़िट अनुक्रम पेड़ के लिए संभव है।एल्गोरिथ्म हमेशा वर्टेक्स 1 से शुरू होता है और पड़ोसियों को किसी भी क्रम में ट्रावर्स कर सकता है। आपके प्रोग्राम को उस स्थिति में
Yes प्रिंट करना चाहिए यदि दिया गया ट्रावर्सल संभव है, अन्यथा No प्रिंट करें।स्मरण रहे कि किसी पेड़ में सदैव
n-1 एजेज़ होती हैं।इनपुट
इनपुट की पहली पंक्ति में एक अकेला पूर्णांक
n (1 ≤ n ≤ 100 000) होता है।अगली
n-1 पंक्तियों में (1 ≤ ≤ n) की जोड़ियाँ होती हैं, जो एजेज़ को दर्शाती हैं।उसके बाद की पंक्ति में
n स्पेस-सेपरेटेड पूर्णांक (1 ≤ ≤ n) होते हैं, जो BFS एल्गोरिथ्म द्वारा विज़िट किए गए वर्टिस के क्रम को दर्शाते हैं।आउटपुट
यदि दिया गया परिदृश्य वैध है, तो प्रोग्राम को
Yes प्रिंट करना चाहिए, अन्यथा No।उदाहरण
Input | Output |
4
1 2
1 3
2 4
1 2 3 4 | Yes |
4
1 2
1 3
2 4
1 2 4 3 | No |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB