oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

gathering_usaco Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

statement.html

Cows have assembled from around the world for a massive gathering. There are N cows, and N-1 pairs of cows who are friends with each other. Every cow knows every other cow through some chain of friendships.

They had great fun, but the time has come for them to leave, one by one. They want to leave in some order such that as long as there are still at least two cows left, every remaining cow has a remaining friend. Furthermore, due to issues with luggage storage, there are M pairs of cows (ai, bi) such that cow ai must leave before cow bi. Note that the cows ai and bi may or may not be friends.

Help the cows figure out, for each cow, whether she could be the last cow to leave. It may be that there is no way for the cows to leave satisfying the above constraints.

INPUT FORMAT:

Line 1 contains two space-separated integers N and M.

Lines 2 ≤ i ≤ N each contain two integers xi and yi with 1 ≤ xi, yi ≤ N and xi yi indicating that cows xi and yi are friends.

Lines N+1 ≤ i ≤ N+M each contain two integers ai and bi with 1 ≤ ai, bi ≤ N and ai ≠ bi indicating that cow ai must leave the gathering before cow bi.

It is guaranteed that 1 ≤ N, M ≤ 105. In test cases worth 20\% of the points, it is further guaranteed that N, M ≤ 3000.

OUTPUT FORMAT (file gathering.out):

The output should consist of N lines, with one integer di on each line such that di = 1 if cow i could be the last to leave, and di = 0 otherwise.

SAMPLE INPUT:

5 1
1 2
2 3
3 4
4 5
2 4

SAMPLE OUTPUT:

0
0
1
1
1

Problem credits: Dhruv Rohatgi

Tags

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100151s256MBAverage
2011s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o gathering_usaco -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.