这么明显的限制条件显然是\(\text{2-sat}\)

考虑按照时间拆点，\((0/1,x,t)\)表示\(x\)个人在时间\(t\)是生/死

有一些显然的连边

\[(0,x,t+1)->(0,x,t)\]

就是如果想在\(t+1\)时刻还是活着那必须在\(t\)时刻还活着

\[(1,x,t)->(1,x,t+1)\]

就是如果\(t\)时刻死了，那么\(t+1\)时刻也得是死的

对于第一种限制，显然是连\((1,x,t)->(1,y,t+1)\)，别忘了连对称边，就是\(y\)在\(t+1\)时刻活着，那么\(x\)在\(t\)时刻可不能死，于是\((0,y,t+1)->(0,x,t)\)

对于第二种限制，连\((0,x,t)->(1,y,t)\)，对称边连\((0,y,t)->(1,x,t)\)

发现按照上面的方式建图我们仅是点数就是\(nT\)级别，不能接受

发现每个人的生/死都连成了一条链，我们把上面每一其他边相连的点缩掉，这样图的点数就达到了\(n+m\)级别

简单分析我们发现这是一个\(\rm DAG\)

要对每个人求出有多少个人能和他一起活到最后

首先如果第\(i\)个人，\((0,i,T+1)\)能走到\((1,i,T+1)\)，即\(i\)活着能推出\(i\)死了，于是\(i\)显然不能活着，自然也就不可能有点能和\(i\)一起活到最后。对于这样的点直接输出\(0\)即可。

否则，我们就看看如果这个点活着，那么能推出多少个点死了，即\((0,i,T+1)\)能到达多少种不同的\((1,y,T+1)\)，这是经典的有向图传递闭包问题，只能做到\(\rm bitset\)复杂度。

那\(\rm bitset\)复杂度就可以了，\(O(\frac{m(n+m)}{w})\)大概就能过了。

但是这样\((0,i,T+1)\)可能没有办法走到那些必死点，我们把必死点做一个\(\rm bitset\)，和\(i\)点的\(\rm bitset\)取一个或就可了。

之后点数大概是\(4\times 10^5\)级别，显然开不下这么大的\(\rm bitset\)。考虑奇技淫巧，我们把\(\rm bitset\)分段，多做几遍就好了

代码

#include
    
     #define re register#define LL long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#pragma GCC optimize(3)#pragma GCC optimize("-fcse-skip-blocks")#define getchar() (S==TT&&(TT=(S=BB)+fread(BB,1,1<<15,stdin),S==TT)?EOF:*S++)char BB[1<<18],*S=BB,*TT=BB; inline int read() {    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;}const int maxn=4.6e5+1;const int W=10000;struct E{int v,nxt;}e[600005];int head[maxn],vis[maxn];std::bitset<10000> dp[maxn],g;std::vector
     
       id[2][50001],ti[50001];int xx[100001],t[100001],yy[100001],op[100001];int n,m,T,cnt,num,chk[50001],ans[50001];inline void add(int x,int y) {e[++num].v=y;e[num].nxt=head[x];head[x]=num;}inline int find(int x,int c) {    int l=0,r=ti[x].size()-1;    while(l<=r) {        int mid=l+r>>1;        if(ti[x][mid]==c) return mid;        if(ti[x][mid]
      
       n) return;r=min(n,r);g.reset();    for(re int i=1;i<=cnt;i++) vis[i]=0,dp[i].reset();    for(re int i=l;i<=r;i++)         for(re int j=0;j