import java.io.IOException;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
 
import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.fs.Path;
import org.apache.hadoop.io.IntWritable;
import org.apache.hadoop.io.Text;
import org.apache.hadoop.mapreduce.Job;
import org.apache.hadoop.mapreduce.Mapper;
import org.apache.hadoop.mapreduce.Reducer;
import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;
 
public class FriendsOfFriends {
 
    public static class FriendsMapper extends Mapper<Object, Text, Text, Text> {
 
        private Text userPair = new Text();
        private Text mutualFriend = new Text();
 
        @Override
        public void map(Object key, Text value, Context context) throws IOException, InterruptedException {
            String[] tokens = value.toString().split("\t");
            if (tokens.length == 2) {
                String user = tokens[0];
                String[] friends = tokens[1].split(",");
                Arrays.sort(friends); // Sort the friends to ensure consistent key ordering
                for (int i = 0; i < friends.length; i++) {
                    for (int j = i + 1; j < friends.length; j++) {
                        userPair.set(friends[i] + "," + friends[j]);
                        mutualFriend.set(user);
                        context.write(userPair, mutualFriend);
                    }
                }
            }
        }
    }
 
    public static class FriendsReducer extends Reducer<Text, Text, Text, IntWritable> {
 
        private IntWritable mutualFriendsCount = new IntWritable();
 
        @Override
        public void reduce(Text key, Iterable<Text> values, Context context)
                throws IOException, InterruptedException {
            Set<String> mutualFriendsSet = new HashSet<>();
            for (Text value : values) {
                mutualFriendsSet.add(value.toString());
            }
            mutualFriendsCount.set(mutualFriendsSet.size());
            context.write(key, mutualFriendsCount);
        }
    }
 
    public static void main(String[] args) throws Exception {
        Configuration conf = new Configuration();
        Job job = Job.getInstance(conf, "FriendsOfFriends");
        job.setJarByClass(FriendsOfFriends.class);
        job.setMapperClass(FriendsMapper.class);
        job.setReducerClass(FriendsReducer.class);
        job.setOutputKeyClass(Text.class);
        job.setOutputValueClass(Text.class);
        FileInputFormat.addInputPath(job, new Path(args[0]));
        FileOutputFormat.setOutputPath(job, new Path(args[1]));
        System.exit(job.waitForCompletion(true) ? 0 : 1);
    }
}

aW1wb3J0IGphdmEuaW8uSU9FeGNlcHRpb247CmltcG9ydCBqYXZhLnV0aWwuQXJyYXlzOwppbXBvcnQgamF2YS51dGlsLkhhc2hTZXQ7CmltcG9ydCBqYXZhLnV0aWwuU2V0OwoKaW1wb3J0IG9yZy5hcGFjaGUuaGFkb29wLmNvbmYuQ29uZmlndXJhdGlvbjsKaW1wb3J0IG9yZy5hcGFjaGUuaGFkb29wLmZzLlBhdGg7CmltcG9ydCBvcmcuYXBhY2hlLmhhZG9vcC5pby5JbnRXcml0YWJsZTsKaW1wb3J0IG9yZy5hcGFjaGUuaGFkb29wLmlvLlRleHQ7CmltcG9ydCBvcmcuYXBhY2hlLmhhZG9vcC5tYXByZWR1Y2UuSm9iOwppbXBvcnQgb3JnLmFwYWNoZS5oYWRvb3AubWFwcmVkdWNlLk1hcHBlcjsKaW1wb3J0IG9yZy5hcGFjaGUuaGFkb29wLm1hcHJlZHVjZS5SZWR1Y2VyOwppbXBvcnQgb3JnLmFwYWNoZS5oYWRvb3AubWFwcmVkdWNlLmxpYi5pbnB1dC5GaWxlSW5wdXRGb3JtYXQ7CmltcG9ydCBvcmcuYXBhY2hlLmhhZG9vcC5tYXByZWR1Y2UubGliLm91dHB1dC5GaWxlT3V0cHV0Rm9ybWF0OwoKcHVibGljIGNsYXNzIEZyaWVuZHNPZkZyaWVuZHMgewoKICAgIHB1YmxpYyBzdGF0aWMgY2xhc3MgRnJpZW5kc01hcHBlciBleHRlbmRzIE1hcHBlcjxPYmplY3QsIFRleHQsIFRleHQsIFRleHQ+IHsKCiAgICAgICAgcHJpdmF0ZSBUZXh0IHVzZXJQYWlyID0gbmV3IFRleHQoKTsKICAgICAgICBwcml2YXRlIFRleHQgbXV0dWFsRnJpZW5kID0gbmV3IFRleHQoKTsKCiAgICAgICAgQE92ZXJyaWRlCiAgICAgICAgcHVibGljIHZvaWQgbWFwKE9iamVjdCBrZXksIFRleHQgdmFsdWUsIENvbnRleHQgY29udGV4dCkgdGhyb3dzIElPRXhjZXB0aW9uLCBJbnRlcnJ1cHRlZEV4Y2VwdGlvbiB7CiAgICAgICAgICAgIFN0cmluZ1tdIHRva2VucyA9IHZhbHVlLnRvU3RyaW5nKCkuc3BsaXQoIlx0Iik7CiAgICAgICAgICAgIGlmICh0b2tlbnMubGVuZ3RoID09IDIpIHsKICAgICAgICAgICAgICAgIFN0cmluZyB1c2VyID0gdG9rZW5zWzBdOwogICAgICAgICAgICAgICAgU3RyaW5nW10gZnJpZW5kcyA9IHRva2Vuc1sxXS5zcGxpdCgiLCIpOwogICAgICAgICAgICAgICAgQXJyYXlzLnNvcnQoZnJpZW5kcyk7IC8vIFNvcnQgdGhlIGZyaWVuZHMgdG8gZW5zdXJlIGNvbnNpc3RlbnQga2V5IG9yZGVyaW5nCiAgICAgICAgICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IGZyaWVuZHMubGVuZ3RoOyBpKyspIHsKICAgICAgICAgICAgICAgICAgICBmb3IgKGludCBqID0gaSArIDE7IGogPCBmcmllbmRzLmxlbmd0aDsgaisrKSB7CiAgICAgICAgICAgICAgICAgICAgICAgIHVzZXJQYWlyLnNldChmcmllbmRzW2ldICsgIiwiICsgZnJpZW5kc1tqXSk7CiAgICAgICAgICAgICAgICAgICAgICAgIG11dHVhbEZyaWVuZC5zZXQodXNlcik7CiAgICAgICAgICAgICAgICAgICAgICAgIGNvbnRleHQud3JpdGUodXNlclBhaXIsIG11dHVhbEZyaWVuZCk7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQoKICAgIHB1YmxpYyBzdGF0aWMgY2xhc3MgRnJpZW5kc1JlZHVjZXIgZXh0ZW5kcyBSZWR1Y2VyPFRleHQsIFRleHQsIFRleHQsIEludFdyaXRhYmxlPiB7CgogICAgICAgIHByaXZhdGUgSW50V3JpdGFibGUgbXV0dWFsRnJpZW5kc0NvdW50ID0gbmV3IEludFdyaXRhYmxlKCk7CgogICAgICAgIEBPdmVycmlkZQogICAgICAgIHB1YmxpYyB2b2lkIHJlZHVjZShUZXh0IGtleSwgSXRlcmFibGU8VGV4dD4gdmFsdWVzLCBDb250ZXh0IGNvbnRleHQpCiAgICAgICAgICAgICAgICB0aHJvd3MgSU9FeGNlcHRpb24sIEludGVycnVwdGVkRXhjZXB0aW9uIHsKICAgICAgICAgICAgU2V0PFN0cmluZz4gbXV0dWFsRnJpZW5kc1NldCA9IG5ldyBIYXNoU2V0PD4oKTsKICAgICAgICAgICAgZm9yIChUZXh0IHZhbHVlIDogdmFsdWVzKSB7CiAgICAgICAgICAgICAgICBtdXR1YWxGcmllbmRzU2V0LmFkZCh2YWx1ZS50b1N0cmluZygpKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBtdXR1YWxGcmllbmRzQ291bnQuc2V0KG11dHVhbEZyaWVuZHNTZXQuc2l6ZSgpKTsKICAgICAgICAgICAgY29udGV4dC53cml0ZShrZXksIG11dHVhbEZyaWVuZHNDb3VudCk7CiAgICAgICAgfQogICAgfQoKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHRocm93cyBFeGNlcHRpb24gewogICAgICAgIENvbmZpZ3VyYXRpb24gY29uZiA9IG5ldyBDb25maWd1cmF0aW9uKCk7CiAgICAgICAgSm9iIGpvYiA9IEpvYi5nZXRJbnN0YW5jZShjb25mLCAiRnJpZW5kc09mRnJpZW5kcyIpOwogICAgICAgIGpvYi5zZXRKYXJCeUNsYXNzKEZyaWVuZHNPZkZyaWVuZHMuY2xhc3MpOwogICAgICAgIGpvYi5zZXRNYXBwZXJDbGFzcyhGcmllbmRzTWFwcGVyLmNsYXNzKTsKICAgICAgICBqb2Iuc2V0UmVkdWNlckNsYXNzKEZyaWVuZHNSZWR1Y2VyLmNsYXNzKTsKICAgICAgICBqb2Iuc2V0T3V0cHV0S2V5Q2xhc3MoVGV4dC5jbGFzcyk7CiAgICAgICAgam9iLnNldE91dHB1dFZhbHVlQ2xhc3MoVGV4dC5jbGFzcyk7CiAgICAgICAgRmlsZUlucHV0Rm9ybWF0LmFkZElucHV0UGF0aChqb2IsIG5ldyBQYXRoKGFyZ3NbMF0pKTsKICAgICAgICBGaWxlT3V0cHV0Rm9ybWF0LnNldE91dHB1dFBhdGgoam9iLCBuZXcgUGF0aChhcmdzWzFdKSk7CiAgICAgICAgU3lzdGVtLmV4aXQoam9iLndhaXRGb3JDb21wbGV0aW9uKHRydWUpID8gMCA6IDEpOwogICAgfQp9