public class BidirectionalMap<TFirst, TSecond> : IEnumerable<KeyValuePair<TFirst, TSecond>>
 {
 private readonly Dictionary<TFirst, TSecond> primary;
 private readonly Dictionary<TSecond, TFirst> secondary;
 public BidirectionalMap()
 {
 primary = new Dictionary<TFirst, TSecond>();
 secondary = new Dictionary<TSecond, TFirst>();
 }
 public BidirectionalMap(int capacity)
 {
 primary = new Dictionary<TFirst, TSecond>(capacity);
 secondary = new Dictionary<TSecond, TFirst>(capacity);
 }
 public BidirectionalMap(IEqualityComparer<TFirst> firstComparer, IEqualityComparer<TSecond> secondComparer)
 {
 primary = new Dictionary<TFirst, TSecond>(firstComparer);
 secondary = new Dictionary<TSecond, TFirst>(secondComparer);
 }
 public BidirectionalMap(IDictionary<TFirst, TSecond> source)
 {
 primary = new Dictionary<TFirst, TSecond>(source);
 secondary = source.ToDictionary(kvp => kvp.Value, kvp => kvp.Key);
 }
 public BidirectionalMap(IDictionary<TSecond, TFirst> source)
 {
 primary = source.ToDictionary(kvp => kvp.Value, kvp => kvp.Key);
 secondary = new Dictionary<TSecond, TFirst>(source);
 }
 public int Count => primary.Count;
 public ICollection<TFirst> PrimaryKeys => primary.Keys;
 public ICollection<TSecond> SecondaryKeys => secondary.Keys;
 // This should be useful only for enumeration by TSecond as key
 public IReadOnlyDictionary<TSecond, TFirst> Inverse => secondary;
 public TSecond this[TFirst first]
 {
 get { return primary[first]; }
 set { Set(first, value); }
 }
 public TFirst this[TSecond second]
 {
 get { return secondary[second]; }
 set { Set(value, second); }
 }
 private void Set(TFirst first, TSecond second)
 {
 // Remove both the entries related to first and second if any
 Remove(first);
 Remove(second);
 // Now it should be safe to add the new relation.
 Add(first, second);
 }
 public void Add(TFirst first, TSecond second)
 {
 try
 {
 primary.Add(first, second);
 }
 catch
 {
 // If the key is present in primary, then we end here and can rethrow with no harm done.
 throw new ArgumentException(nameof(first), $"{first} already present in the dictionary");
 }
 try
 {
 secondary.Add(second, first);
 }
 catch 
 {
 // If second exists in secondary, secondary throws, and primary must be rolled back - because first was added successfully
 primary.Remove(first);
 throw new ArgumentException(nameof(second), $"{second} already present in the dictionary");
 }
 }
 public bool Remove(TFirst first)
 {
 if (primary.TryGetValue(first, out var second))
 {
 secondary.Remove(second);
 primary.Remove(first);
 return true;
 }
 return false;
 }
 public bool Remove(TSecond second)
 {
 if (secondary.TryGetValue(second, out var first))
 {
 primary.Remove(first);
 secondary.Remove(second);
 return true;
 }
 return false;
 }
 public bool TryGetValue(TFirst first, out TSecond second)
 {
 return primary.TryGetValue(first, out second);
 }
 public bool TryGetValue(TSecond second, out TFirst first)
 {
 return secondary.TryGetValue(second, out first);
 }
 public bool Contains(TFirst first)
 {
 return primary.ContainsKey(first);
 }
 public bool Contains(TSecond second)
 {
 return secondary.ContainsKey(second);
 }
 public void Clear()
 {
 primary.Clear();
 secondary.Clear();
 }
 public IEnumerator<KeyValuePair<TFirst, TSecond>> GetEnumerator()
 {
 return primary.GetEnumerator();
 }
 IEnumerator IEnumerable.GetEnumerator()
 {
 return GetEnumerator();
 }
 }

 [TestClass]
 public class BidirectionalMapTests
 {
 [TestMethod]
 public void InitializeFromSourceDictionary()
 {
 Dictionary<string, int> source = new Dictionary<string, int>
 {
 { "a", 1 },
 { "b", 2 }
 };
 BidirectionalMap<string, int> map = new BidirectionalMap<string, int>(source);
 Assert.AreEqual(1, map["a"]);
 Assert.AreEqual("b", map[2]);
 }
 [TestMethod]
 public void Add()
 {
 BidirectionalMap<string, int> map = new BidirectionalMap<string, int>();
 map.Add("a", 1);
 map.Add("b", 2);
 Assert.AreEqual(1, map["a"]);
 Assert.AreEqual("b", map[2]);
 Assert.AreEqual(2, map.Count);
 }
 [TestMethod]
 public void InvalidAdd()
 {
 BidirectionalMap<string, int> map = new BidirectionalMap<string, int>();
 map.Add("a", 1);
 Assert.ThrowsException<ArgumentException>(() => map.Add("a", 2));
 Assert.ThrowsException<ArgumentException>(() => map.Add("b", 1));
 Assert.AreEqual(1, map["a"]);
 }
 [TestMethod]
 public void Remove()
 {
 BidirectionalMap<string, int> map = new BidirectionalMap<string, int>();
 map.Add("a", 1);
 map.Add("b", 2);
 map.Remove("a");
 map.Remove(2);
 Assert.AreEqual(0, map.Count);
 }
 [TestMethod]
 public void RemoveNonExistingValue()
 {
 BidirectionalMap<string, int> map = new BidirectionalMap<string, int>();
 map.Add("a", 1);
 map.Add("b", 2);
 map.Remove("c");
 Assert.AreEqual(2, map.Count);
 }
 [TestMethod]
 public void Set()
 {
 BidirectionalMap<string, int> map = new BidirectionalMap<string, int>();
 map.Add("a", 1);
 map.Add("b", 2);
 map["a"] = 3;
 Assert.AreEqual(2, map.Count);
 Assert.IsTrue(map.TryGetValue("a", out int second));
 Assert.AreEqual(3, second);
 }
 [TestMethod]
 public void SetWithExistingSecondValue()
 {
 BidirectionalMap<string, int> map = new BidirectionalMap<string, int>();
 map.Add("a", 1);
 map.Add("b", 2);
 map["a"] = 2;
 Assert.AreEqual(1, map.Count);
 Assert.IsTrue(map.TryGetValue("a", out int second));
 Assert.AreEqual(2, second);
 Assert.IsFalse(map.TryGetValue("b", out _));
 }
 [TestMethod]
 public void TryGetValue()
 {
 BidirectionalMap<string, int> map = new BidirectionalMap<string, int>();
 map.Add("a", 1);
 map.Add("b", 2);
 Assert.IsTrue(map.TryGetValue("a", out int second));
 Assert.AreEqual(1, second);
 Assert.IsTrue(map.TryGetValue(2, out string first));
 Assert.AreEqual("b", first);
 }
 }

 /// <summary>
 /// A one-one relation bidirectional map.
 /// <para>
 /// A one-one relation means that each entry of type <typeparamref name="TFirst"/> can correspond to exactly one 
 /// entry of type <typeparamref name="TSecond"/> and visa versa.
 /// </para>
 /// The map doesn't support null objects because each element is both key and value in its relation and keys can't be null.
 /// </summary>
 /// <typeparam name="TFirst">Any type</typeparam>
 /// <typeparam name="TSecond">Any type</typeparam>
 public class BidirectionalMap<TFirst, TSecond> : IEnumerable<KeyValuePair<TFirst, TSecond>>
 {
 private readonly Dictionary<TFirst, TSecond> primary;
 private readonly Dictionary<TSecond, TFirst> secondary;
 public BidirectionalMap()
 {
 primary = new Dictionary<TFirst, TSecond>();
 secondary = new Dictionary<TSecond, TFirst>();
 }
 /// <summary>
 /// Creates a BidirectionalMap initialized with the specified <paramref name="capacity"/>.
 /// </summary>
 /// <param name="capacity">The desired capacity for the map.</param>
 /// <exception cref="ArgumentOutOfRangeException">If capacity is out of range (&lt; 0)</exception>
 public BidirectionalMap(int capacity)
 {
 primary = new Dictionary<TFirst, TSecond>(capacity);
 secondary = new Dictionary<TSecond, TFirst>(capacity);
 }
 /// <summary>
 /// Creates a BidirectionalMap with the specified equality comparers.
 /// </summary>
 /// <param name="firstComparer">Equality comparer for <typeparamref name="TFirst"/>. If null, the default comparer is used.</param>
 /// <param name="secondComparer">Equality comparer for <typeparamref name="TSecond"/>. If null, the default comparer is used.</param>
 public BidirectionalMap(IEqualityComparer<TFirst> firstComparer, IEqualityComparer<TSecond> secondComparer)
 {
 primary = new Dictionary<TFirst, TSecond>(firstComparer);
 secondary = new Dictionary<TSecond, TFirst>(secondComparer);
 }
 /// <summary>
 /// Creates a BidirectionalMap from the <paramref name="source"/> dictionary.
 /// </summary>
 /// <param name="source">The source dictionary from which to create a one-one relation map</param>
 /// <exception cref="ArgumentException">If <paramref name="source"/> contains doublets in values</exception>
 /// <exception cref="ArgumentNullException">If <paramref name="source"/> contains null values</exception>
 public BidirectionalMap(IDictionary<TFirst, TSecond> source)
 {
 primary = new Dictionary<TFirst, TSecond>(source);
 secondary = source.ToDictionary(kvp => kvp.Value, kvp => kvp.Key);
 }
 /// <summary>
 /// Creates a BidirectionalMap from the <paramref name="inverseSource"/> dictionary.
 /// </summary>
 /// <param name="inverseSource">The source dictionary from which to create a one-one relation map</param>
 /// <exception cref="ArgumentException">If <paramref name="inverseSource"/> contains doublets in values</exception>
 /// <exception cref="ArgumentNullException">If <paramref name="inverseSource"/> contains null values</exception>
 public BidirectionalMap(IDictionary<TSecond, TFirst> inverseSource)
 {
 primary = inverseSource.ToDictionary(kvp => kvp.Value, kvp => kvp.Key);
 secondary = new Dictionary<TSecond, TFirst>(inverseSource);
 }
 public int Count => primary.Count;
 public ICollection<TFirst> PrimaryKeys => primary.Keys;
 public ICollection<TSecond> SecondaryKeys => secondary.Keys;
 // This should be useful only for enumeration by TSecond as key
 public IReadOnlyDictionary<TSecond, TFirst> Inverse => secondary;
 public TSecond this[TFirst first]
 {
 get { return primary[first]; }
 set { Set(first, value); }
 }
 public TFirst this[TSecond second]
 {
 get { return secondary[second]; }
 set { Set(value, second); }
 }
 private void Set(TFirst first, TSecond second)
 {
 // Remove both the entries related to first and second if any
 Remove(first);
 Remove(second);
 // Now it should be safe to add the new relation.
 Add(first, second);
 }
 public void Add(TFirst first, TSecond second)
 {
 try
 {
 primary.Add(first, second);
 }
 catch (ArgumentNullException)
 {
 // If first is null, we end here and can rethrow with no harm done.
 throw new ArgumentNullException(nameof(first));
 }
 catch (ArgumentException)
 {
 // If the key is present in primary, then we end here and can rethrow with no harm done.
 throw new ArgumentException(nameof(first), $"{first} already present in the dictionary");
 }
 try
 {
 secondary.Add(second, first);
 }
 catch (ArgumentNullException)
 {
 // If second is null, we end here, and primary must be rolled back - because first was added successfully
 primary.Remove(first);
 throw new ArgumentNullException(nameof(second));
 }
 catch (ArgumentException)
 {
 // If second exists in secondary, secondary throws, and primary must be rolled back - because first was added successfully
 primary.Remove(first);
 throw new ArgumentException(nameof(second), $"{second} already present in the dictionary");
 }
 }
 public bool Remove(TFirst first)
 {
 if (primary.TryGetValue(first, out var second))
 {
 secondary.Remove(second);
 primary.Remove(first);
 return true;
 }
 return false;
 }
 public bool Remove(TSecond second)
 {
 if (secondary.TryGetValue(second, out var first))
 {
 primary.Remove(first);
 secondary.Remove(second);
 return true;
 }
 return false;
 }
 public bool TryGetValue(TFirst first, out TSecond second)
 {
 return primary.TryGetValue(first, out second);
 }
 public bool TryGetValue(TSecond second, out TFirst first)
 {
 return secondary.TryGetValue(second, out first);
 }
 public bool Contains(TFirst first)
 {
 return primary.ContainsKey(first);
 }
 public bool Contains(TSecond second)
 {
 return secondary.ContainsKey(second);
 }
 public void Clear()
 {
 primary.Clear();
 secondary.Clear();
 }
 public IEnumerator<KeyValuePair<TFirst, TSecond>> GetEnumerator()
 {
 return primary.GetEnumerator();
 }
 IEnumerator IEnumerable.GetEnumerator()
 {
 return GetEnumerator();
 }
 }

 [TestClass]
 public class BidirectionalMapTests
 {
 class TestObject<T>
 {
 public TestObject(T value)
 {
 Value = value;
 }
 public T Value { get; }
 public static implicit operator T(TestObject<T> to) => to.Value;
 public static implicit operator TestObject<T>(T value) => new TestObject<T>(value);
 public override string ToString()
 {
 return Value?.ToString() ?? "";
 }
 }
 [TestMethod]
 public void InitializeFromSourceDictionary()
 {
 Dictionary<string, int> source = new Dictionary<string, int>
 {
 { "a", 1 },
 { "b", 2 }
 };
 BidirectionalMap<string, int> map = new BidirectionalMap<string, int>(source);
 Assert.AreEqual(1, map["a"]);
 Assert.AreEqual("b", map[2]);
 }
 [TestMethod]
 public void InvalidInitializeFromSourceDictionary()
 {
 TestObject<string> one = new TestObject<string>("1");
 Dictionary<string, TestObject<string>> source = new Dictionary<string, TestObject<string>>
 {
 { "a", one },
 { "b", one }
 };
 BidirectionalMap<string, TestObject<string>> map = null;
 Assert.ThrowsException<ArgumentException>(() => map = new BidirectionalMap<string, TestObject<string>>(source));
 Dictionary<TestObject<string>, string> inverseSource = new Dictionary<TestObject<string>, string>
 {
 { "a", "1" },
 { "b", "1" }
 };
 Assert.ThrowsException<ArgumentException>(() => map = new BidirectionalMap<string, TestObject<string>>(inverseSource));
 source = new Dictionary<string, TestObject<string>>
 {
  { "a", null },
 { "b", "1" }
 };
 Assert.ThrowsException<ArgumentNullException>(() => map = new BidirectionalMap<string, TestObject<string>>(source));
 }
 [TestMethod]
 public void Add()
 {
 BidirectionalMap<string, int> map = new BidirectionalMap<string, int>();
 map.Add("a", 1);
 map.Add("b", 2);
 Assert.AreEqual(1, map["a"]);
 Assert.AreEqual("b", map[2]);
 Assert.AreEqual(2, map.Count);
 }
 [TestMethod]
 public void InvalidAdd()
 {
 BidirectionalMap<string, int> map = new BidirectionalMap<string, int>();
 map.Add("a", 1);
 Assert.ThrowsException<ArgumentException>(() => map.Add("a", 2));
 Assert.ThrowsException<ArgumentException>(() => map.Add("b", 1));
 Assert.AreEqual(1, map["a"]);
 }
 [TestMethod]
 public void AddNull()
 {
  BidirectionalMap<string, string> map = new BidirectionalMap<string, string>();
 Assert.ThrowsException<ArgumentNullException>(() => map.Add(null, "a"));
 Assert.ThrowsException<ArgumentNullException>(() => map.Add("a", null));
 Assert.AreEqual(0, map.Count);
 }
 [TestMethod]
 public void Remove()
 {
 BidirectionalMap<string, int> map = new BidirectionalMap<string, int>();
 map.Add("a", 1);
 map.Add("b", 2);
 Assert.AreEqual(2, map.Count);

 map.Remove("a");
 Assert.AreEqual(1, map.Count);
 map.Remove(2);
 Assert.AreEqual(0, map.Count);
 }
 [TestMethod]
 public void RemoveNonExistingValue()
 {
 BidirectionalMap<string, int> map = new BidirectionalMap<string, int>();
 map.Add("a", 1);
 map.Add("b", 2);
 Assert.IsFalse(map.Remove("c"));
 Assert.AreEqual(2, map.Count);
 }
 [TestMethod]
 public void Set()
 {
 BidirectionalMap<string, int> map = new BidirectionalMap<string, int>();
 map.Add("a", 1);
 map.Add("b", 2);
 map["a"] = 3;
 Assert.AreEqual(2, map.Count);
 Assert.IsTrue(map.TryGetValue("a", out int second));
 Assert.AreEqual(3, second);
 Assert.IsTrue(map.TryGetValue(3, out string first));
 Assert.AreEqual("a", first);
 Assert.IsFalse(map.TryGetValue(1, out _));
 }
 [TestMethod]
 public void SetWithExistingSecondValue()
 {
 BidirectionalMap<string, int> map = new BidirectionalMap<string, int>();
 map.Add("a", 1);
 map.Add("b", 2);
 map["a"] = 2;
 Assert.AreEqual(1, map.Count);
 Assert.IsTrue(map.TryGetValue("a", out int second));
 Assert.AreEqual(2, second);
 Assert.IsTrue(map.TryGetValue(2, out string first));
 Assert.AreEqual("a", first);
 Assert.IsFalse(map.TryGetValue("b", out _));
 }
 [TestMethod]
 public void TryGetValue()
 {
 BidirectionalMap<string, int> map = new BidirectionalMap<string, int>
 {
  { "a", 1 },
  { "b", 2 }
 };
 Assert.IsTrue(map.TryGetValue("a", out int second));
 Assert.AreEqual(1, second);
 Assert.IsTrue(map.TryGetValue(2, out string first));
 Assert.AreEqual("b", first);
 Assert.IsFalse(map.TryGetValue("c", out _));
 Assert.IsFalse(map.TryGetValue(3, out _));
 }
 }

I think that the naming TFirst, TSecond, primary and secondary could be better in order to reflect their equal status, but I didn't find any better. May be you have any suggestions?