A software development competition sent an email to the members of the winning projects. The email didn't mention the winning projects. Each person can participate in multiple projects, but they will receive an email if at least one of their projects was a winning project.
Given the projects, their members, and the list of people that received the email. Print the list of projects that won for sure.
A person can win multiple times for multiple projects, but they would be mentioned only once in the email.
The first line of input contains two integers $n$ and $m$ $(1 \leq n,m \leq 10^6),$ the number of projects and the number of participants, respectively.
The second line contains an integer $q$ and a list $a$ $(1 \leq q, a_i \leq m)$, where $q$ is the number of participants that received the email, and the $a$ is the list of participants that received the email.
The ith of the following $n$ lines contains an integer $w_i$ and a list $x$ $(1 \leq w_i, x_j \leq m)$, where $w_i$ is the number of members of the $i^{th}$ project, and $x$ is a list of size $w_i$ containing the members of that project.
Note: $\sum_{i=1}^{n} w_i \leq 2*10^6 $
On the first line, print the number of projects that won for sure.
On the second line, print a sorted list of the winning projects.
| Input | Output |
|---|---|
3 3 2 1 2 3 1 2 3 2 1 2 2 2 3 Copy
|
1 2 Copy
|
4 3 3 1 2 3 2 1 2 2 2 3 2 1 3 3 1 2 3 Copy
|
0 Copy
|
Remove the projects that have non-winning members, then the projects that are winning are the projects that have at least one member with only this project remaining after removal.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());
const int N = 1e6;
vector<int>ans;
int n,m,q;
bool seen[N];
vector<int>v[N],is[N];
int main(){
scanf("%d%d%d",&amp;n,&amp;m,&amp;q);
for(int i = 0,a;i < q;i++){
scanf("%d",&amp;a);
seen[a - 1] = 1;
}
for(int i = 0;i < n;i++){
scanf("%d",&amp;q);
vector<int>temp;
bool bad = 0;
for(int j = 0,a;j < q;j++){
scanf("%d",&amp;a);
temp.push_back(a - 1);
bad|=!seen[a - 1];
}
if(bad)continue;
for(auto j : temp)is[j].push_back(i);
}
for(int i = 0;i < m;i++)
if(is[i].size() == 1)ans.push_back(is[i][0] + 1);
sort(ans.begin(),ans.end());
ans.resize(unique(ans.begin(),ans.end()) - ans.begin());
printf("%d\n",ans.size());
for(auto i : ans)printf("%d ",i);
puts("");
}