TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3113
  • Problem
  • P3113[CF576E] 给边涂色 Painting Edges
    Limits : Time Limit : - MS   Memory Limit : 786432 KB
    Judgment Tips : 6s,768MB
    Description

    给定一个 \(n\) 个节点和 \(m\) 条边组成的无向图。节点编号为 $1\sim n$ ,边的编号为 $1\sim m$ 。每条边可以没有颜色,也可以涂成 $1\sim k$ 中的某种颜色。最初任何边都没有颜色。

    你将得到一些形如“将边 \(e_i\) 涂成颜色 \(c_i\) ”的请求,你必须保证任何时候被涂成同种颜色边构成的图示一个二分图。如果一个请求会违反这个条件则这个请求无效,边 \(e_i\) 保留原来的颜色(或者保持无色);否则就执行这个请求所描述的涂色操作。总共有 \(q\) 个请求,你的任务是汇报每条请求是否被执行。

    Input Format

    第一行四个整数 \(n,m,k,q\) ,分别是节点数、边数、颜色数、请求数。

    接下来 \(m\) 行,每行两个整数 \(a_i,b_i(1\leq a_i,b_i\leq n)\) ,表示一条边。保证没有重边和自环。

    接下来 \(q\) 行,每行两个整数 \(e_i,c_i(1\leq e_i\leq m,1\leq c_i\leq k)\) ,表示一条请求。

    Output Format

    每条请求输出一行,如果被执行输出 YES ,否则输出 NO

    Sample Input

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

    Sample Output

    YES
    YES
    YES
    NO
    YES

    Hint

    $2\leq n\leq 5\times 10^5$
    $1\leq m,q\leq 5\times 10^5$
    $1\leq k\leq 50$


    Source  CF576E nodgd搬运并提供数据