Ալգորիթմներ և Տվյալների Կառուցվածքներ

Գրաֆի էֆեկտիվության ստուգումը

Տրված է չուղղորդված գրաֆ, որն ունի v գագաթ և e եզր: Ձեզ խնդրում են ստուգել, թե արդյոք գրաֆը էֆեկտիվ է։ Գրաֆը համարվում է էֆեկտիվ, եթե յուրաքանչյուր գագաթից կարելի է հասնել ցանկացած այլ գագաթի, անցնելով ամենաշատը 2 եզր։

Մուտք

Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր v (1 ≤ v ≤ 100) և e (1 ≤ e ≤ 10 000)։

Հաջորդ e տողերիցcada մեկը պարունակում է երկու ամբողջ թվեր v1 և v2 (1 ≤ v1, v2 ≤ v), որոնք ցույց են տալիս, որ գագաթ v1-ը կապված է գագաթ v2-ի հետ։

Ելք

Ծրագիրը ելքում պետք է տպի Yes, եթե գրաֆը էֆեկտիվ է, հակառակ դեպքում՝ No։

Օրինակներ

Մուտք

Ելք

4 3
1 2
2 3
3 1

No

4 4
1 2
2 3
3 1
1 4

Yes

Շարադրանք

  1. 4-րդ գագաթը մյուսների հետ կապ չունի, հետևաբար 4-րդ գագաթից ոչ մի այլ գագաթի հնարավոր չէ հասնել առավելագույնը 2 եզրով։

  2. Ցանկացած գագաթից հնարավոր է հասնել ցանկացած այլ գագաթի, անցնելով ամենաշատը 2 եզր։

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue